//===--- DiverseStack.h - Stack of variably-sized objects -------*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
///
/// \file
///
/// This file defines a m_data structure for representing a stack of
/// variably-sized objects.  It is a requirement that the object type
/// be trivially movable, meaning that iter has a trivial move
/// constructor and a trivial destructor.
///
//===----------------------------------------------------------------------===//

#ifndef POLARPHP_BASIC_DIVERSE_STACK_H
#define POLARPHP_BASIC_DIVERSE_STACK_H

#include "polarphp/basic/Malloc.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/PointerLikeTypeTraits.h"
#include <cassert>
#include <cstring>
#include <utility>

namespace polar {

template <class T> class DiverseStackImpl;

/// DiverseStack - A stack of heterogeneously-typed objects.
///
/// \tparam T - A common base class of the objects on the stack; must
///   provide an allocated_size() const method.
/// \tparam InlineCapacity - the amount of inline storage to provide, in bytes.
template <class T, unsigned InlineCapacity>
class DiverseStack : public DiverseStackImpl<T> {
   char InlineStorage[InlineCapacity];

public:
   DiverseStack() : DiverseStackImpl<T>(InlineStorage + InlineCapacity) {}
   DiverseStack(const DiverseStack &other)
      : DiverseStackImpl<T>(other, InlineStorage + InlineCapacity) {}
   DiverseStack(const DiverseStackImpl<T> &other)
      : DiverseStackImpl<T>(other, InlineStorage + InlineCapacity) {}
   DiverseStack(DiverseStack<T, InlineCapacity> &&other)
      : DiverseStackImpl<T>(std::move(other), InlineStorage + InlineCapacity) {}
   DiverseStack(DiverseStackImpl<T> &&other)
      : DiverseStackImpl<T>(std::move(other), InlineStorage + InlineCapacity) {}
};

/// A base class for DiverseStackImpl.
class DiverseStackBase {
public:
   /// The top of the stack.
   char *Begin;

   /// The bottom of the stack, i.e. the end of the allocation.
   char *End;

   /// The beginning of the allocation.
   char *Allocated;

   bool isAllocatedInline() const {
      return (Allocated == reinterpret_cast<const char *>(this + 1));
   }

   void checkValid() const {
      assert(Allocated <= Begin);
      assert(Begin <= End);
   }

   void initialize(char *end) {
      Begin = End = end;
      Allocated = reinterpret_cast<char*>(this + 1);
   }
   void copyFrom(const DiverseStackBase &other) {
      // Ensure that we're large enough to store all the data.
      std::size_t size = static_cast<std::size_t>(other.End - other.Begin);
      pushNewStorage(size);
      std::memcpy(Begin, other.Begin, size);
   }
   void pushNewStorage(std::size_t needed) {
      checkValid();
      if (std::size_t(Begin - Allocated) >= needed) {
         Begin -= needed;
      } else {
         pushNewStorageSlow(needed);
      }
   }
   void pushNewStorageSlow(std::size_t needed);

   /// A stable iterator is the equivalent of an index into the stack.
   /// It's an iterator that stays stable across modification of the
   /// stack.
   class stable_iterator {
      std::size_t Depth;
      friend class DiverseStackBase;
      template <class T> friend class DiverseStackImpl;
      stable_iterator(std::size_t depth) : Depth(depth) {}
   public:
      stable_iterator() = default;
      friend bool operator==(stable_iterator a, stable_iterator b) {
         return a.Depth == b.Depth;
      }
      friend bool operator!=(stable_iterator a, stable_iterator b) {
         return !operator==(a, b);
      }

      static stable_iterator invalid() {
         return stable_iterator((std::size_t) -1);
      }
      bool isValid() const {
         return Depth != (std::size_t) -1;
      }

      std::size_t getDepth() const { return Depth; }

      /// A helper class that wraps a stable_iterator as something that
      /// pretends to be a non-null pointer.
      ///
      /// This allows stable_iterators to be placed in TinyPtrVector.
      ///
      /// A wrapper is needed because we don't want to give stable_iterator
      /// a null inhabitant, an operator bool, conversions from nullptr_t, or
      /// any similar features that TinyPtrVector reasonably requires of its
      /// element types.
      class AsPointer {
         void *EncodedValue;
         explicit AsPointer(void *encodedValue) : EncodedValue(encodedValue) {}
      public:
         enum { NumLowBitsAvailable = 3 };

         /// Allow a null AsPointer to be created with either 'nullptr' or
         /// 'AsPointer()'.
         /*implicit*/ AsPointer(std::nullptr_t _ = nullptr)
            : EncodedValue(nullptr) {}

         /// Allow an AsPointer to be tested as a boolean value.
         explicit operator bool() const { return EncodedValue != nullptr; }

         /// Allow an AsPointer to be compared for equality with a void*.
         friend bool operator==(AsPointer lhs, void *rhs) {
            return lhs.EncodedValue == rhs;
         }

         /// Allow an implicit conversion from stable_iterator.
         /*implicit*/ AsPointer(stable_iterator it) {
            assert(it.isValid() && "can't encode invalid stable_iterator");
            auto encodedDepth = (it.Depth + 1) << NumLowBitsAvailable;
            EncodedValue = reinterpret_cast<void*>(encodedDepth);
            assert(EncodedValue && "encoded pointer was null");
         }

         /// Allow an implicit conversion to stable_iterator.
         operator stable_iterator() const {
            assert(EncodedValue && "can't decode null pointer");
            auto encodedDepth = reinterpret_cast<std::size_t>(EncodedValue);
            auto depth = (encodedDepth >> NumLowBitsAvailable) - 1;
            auto it = stable_iterator(depth);
            assert(it.isValid() && "decoded stable_iterator was invalid");
            return it;
         }

         void *getAsVoidPointer() const { return EncodedValue; }
         static AsPointer getFromVoidPointer(void *ptr) { return AsPointer(ptr); }
      };
      AsPointer asPointer() const { return *this; }
   };
   stable_iterator stable_begin() const {
      return stable_iterator(End - Begin);
   }
   static stable_iterator stable_end() {
      return stable_iterator(0);
   }

   void checkIterator(stable_iterator it) const {
      assert(it.isValid() && "checking an invalid iterator");
      checkValid();
      assert(it.Depth <= size_t(End - Begin));
   }
};

template <class T> class DiverseStackImpl : private DiverseStackBase {
   DiverseStackImpl(const DiverseStackImpl<T> &other) = delete;
   DiverseStackImpl(DiverseStackImpl<T> &&other) = delete;

protected:
   DiverseStackImpl(char *end) {
      initialize(end);
   }

   DiverseStackImpl(const DiverseStackImpl<T> &other, char *end) {
      initialize(end);
      copyFrom(other);
   }
   DiverseStackImpl(DiverseStackImpl<T> &&other, char *end) {
      // If the other is allocated inline, just initialize and copy.
      if (other.isAllocatedInline()) {
         initialize(end);
         copyFrom(other);
         return;
      }

      // Otherwise, steal its allocations.
      Begin = other.Begin;
      End = other.End;
      Allocated = other.Allocated;
      other.Begin = other.End = other.Allocated = (char*) (&other + 1);
      assert(other.isAllocatedInline());
   }

public:
   ~DiverseStackImpl() {
      checkValid();
      if (!isAllocatedInline())
         delete[] Allocated;
   }

   /// Query whether the stack is empty.
   bool empty() const {
      checkValid();
      return Begin == End;
   }

   /// Return a reference to the top element on the stack.
   T &top() {
      assert(!empty());
      return *reinterpret_cast<T*>(Begin);
   }

   /// Return a reference to the top element on the stack.
   const T &top() const {
      assert(!empty());
      return *reinterpret_cast<const T*>(Begin);
   }

   using DiverseStackBase::stable_iterator;
   using DiverseStackBase::stable_begin;
   using DiverseStackBase::stable_end;

   class const_iterator;
   class iterator {
      char *Ptr;
      friend class DiverseStackImpl;
      friend class const_iterator;
      iterator(char *ptr) : Ptr(ptr) {}

   public:
      iterator() = default;

      T &operator*() const { return *reinterpret_cast<T*>(Ptr); }
      T *operator->() const { return reinterpret_cast<T*>(Ptr); }
      iterator &operator++() {
         Ptr += (*this)->allocated_size();
         return *this;
      }
      iterator operator++(int _) {
         auto copy = *this;
         operator++();
         return copy;
      }

      /// advancePast - Like operator++, but asserting that the current
      /// object has a known type.
      template <class U> void advancePast() {
         assert((*this)->allocated_size() == sizeof(U));
         Ptr += sizeof(U);
      }

      friend bool operator==(iterator a, iterator b) { return a.Ptr == b.Ptr; }
      friend bool operator!=(iterator a, iterator b) { return !operator==(a, b); }
   };

   using DiverseStackBase::checkIterator;
   void checkIterator(iterator it) const {
      checkValid();
      assert(Begin <= it.Ptr && it.Ptr <= End);
   }

   iterator begin() { checkValid(); return iterator(Begin); }
   iterator end() { checkValid(); return iterator(End); }
   iterator find(stable_iterator it) {
      checkIterator(it);
      return iterator(End - it.Depth);
   }
   stable_iterator stabilize(iterator it) const {
      checkIterator(it);
      return stable_iterator(End - it.Ptr);
   }

   T &findAndAdvance(stable_iterator &i) {
      auto unstable_i = find(i);
      assert(unstable_i != end());
      T &value = *unstable_i;
      ++unstable_i;
      i = stabilize(unstable_i);
      return value;
   }

   class const_iterator {
      const char *Ptr;
      friend class DiverseStackImpl;
      const_iterator(const char *ptr) : Ptr(ptr) {}
   public:
      const_iterator() = default;
      const_iterator(iterator it) : Ptr(it.Ptr) {}

      const T &operator*() const { return *reinterpret_cast<const T*>(Ptr); }
      const T *operator->() const { return reinterpret_cast<const T*>(Ptr); }
      const_iterator &operator++() {
         Ptr += (*this)->allocated_size();
         return *this;
      }
      const_iterator operator++(int _) {
         auto copy = *this;
         operator++();
         return copy;
      }

      /// advancePast - Like operator++, but asserting that the current
      /// object has a known type.
      template <class U> void advancePast() {
         assert((*this)->allocated_size() == sizeof(U));
         Ptr += sizeof(U);
      }

      friend bool operator==(const_iterator a, const_iterator b) {
         return a.Ptr == b.Ptr;
      }
      friend bool operator!=(const_iterator a, const_iterator b) {
         return !operator==(a, b);
      }
   };
   const_iterator begin() const { checkValid(); return const_iterator(Begin); }
   const_iterator end() const { checkValid(); return const_iterator(End); }
   void checkIterator(const_iterator it) const {
      checkValid();
      assert(Begin <= it.Ptr && it.Ptr <= End);
   }
   const_iterator find(stable_iterator it) const {
      checkIterator(it);
      return const_iterator(End - it.Depth);
   }
   stable_iterator stabilize(const_iterator it) const {
      checkIterator(it);
      return stable_iterator(End - it.Ptr);
   }

   /// Push a new object onto the stack.
   template <class U, class... A> U &push(A && ...args) {
      pushNewStorage(sizeof(U));
      return *::new (Begin) U(::std::forward<A>(args)...);
   }

   /// Pop an object off the stack.
   void pop() {
      assert(!empty());
      Begin += top().allocated_size();
   }

   /// Pop an object of known type off the stack.
   template <class U> void pop() {
      assert(!empty());
      assert(sizeof(U) == top().allocated_size());
      Begin += sizeof(U);
   }

   /// Pop objects off of the stack until \p the object pointed to by stable_iter
   /// is the top element of the stack.
   void pop(stable_iterator stable_iter) {
      iterator iter = find(stable_iter);
      checkIterator(iter);
#ifndef NDEBUG
      while (Begin != iter.Ptr) {
         pop();
         checkIterator(iter);
      }
#else
      Begin = iter.Ptr;
#endif
   }
};

/// A helper class for copying value off a DiverseStack.
template <class T>
class DiverseValueBuffer {
   llvm::SmallVector<char, sizeof(T) + 10 * sizeof(void*)> data;

public:
   DiverseValueBuffer(const T &value) {
      size_t size = value.allocated_size();
      data.reserve(size);
      data.set_size(size);
      memcpy(data.data(), reinterpret_cast<const void *>(&value), size);
   }

   T &getCopy() { return *reinterpret_cast<T *>(data.data()); }
};
} // end namespace polar

/// Allow stable_iterators to be put in things like TinyPtrVectors.
namespace llvm {
template <>
struct PointerLikeTypeTraits<
   polar::DiverseStackBase::stable_iterator::AsPointer> {
   using AsPointer = polar::DiverseStackBase::stable_iterator::AsPointer;
public:
   static inline void *getAsVoidPointer(AsPointer ptr) {
      return ptr.getAsVoidPointer();
   }
   static inline AsPointer getFromVoidPointer(void *ptr) {
      return AsPointer::getFromVoidPointer(ptr);
   }

   enum {
      NumLowBitsAvailable = AsPointer::NumLowBitsAvailable
   };
};
}

#endif // POLARPHP_BASIC_DIVERSE_STACK_H
